// 备用文件,存放一些不知道有没有用的库函数

// 堆
function Heap( basicSize ) {
	var i = 0;
	// 确保basicSize是2的次幂
	if ( ( basicSize & ( basicSize - 1 ) ) !== 0 ) {
		while ( basicSize !== 0 ) {
			basicSize >>= 1;
			++i;
		}

		basicSize = 1 << i;
	}

	var capacity = basicSize; // 总容量
	var remindSize = basicSize - 1; // 剩余尺寸,注意0号位不用
	var heap = Array( basicSize ); // 堆数组
	var values = Array( basicSize ); // 值数组

	// 初始化堆
	function initHeap( start, end, k ) {
		var i;

		// 初始化
		for ( i = start; i != end; ++i, ++k ) {
			heap[i] = k;
		}
	}

	initHeap( 0, capacity, 0 );

	// 重新设置容量,容量设置为元容量的两倍
	function recapacity() {
		// 分配空间并初始化堆
		heap = heap.concat( Array( capacity ) );
		values = values.concat( Array( capacity ) );
		initHeap( 1, 1 + capacity, capacity );

		// 更新相关属性
		remindSize += capacity;
		capacity *= 2;
	}

	function swap( pos1, pos2 ) {
		var tmp = heap[pos1];
		heap[pos1] = heap[pos2];
		heap[pos2] = tmp;
	}

	// 指定节点向上渗透
	function perUp( pos ) {
		var son;
		while ( pos !== 1 ) {
			son = Math.floor( pos / 2 );
			if ( heap[pos] < heap[son] ) {
				swap( pos, son );
			}
			pos = son;
		}
	}

	// 指定节点向下渗透
	function perDown( pos ) {
		var father;
		while ( pos * 2 <= remindSize ) {
			father = pos * 2;
			father = father === remindSize ? father : heap[father] < heap[father + 1] ? father : father + 1;
			if ( heap[pos] > heap[father] ) {
				swap( pos, father );
			}
			pos = father;
		}
	}

	return {
		alloc : function( val ) {
			var retVal;
			// 如果空间不足则重新分配空间
			if ( remindSize === 0 ) {
				recapacity();
			}

			// 取走heap[1],并更新堆
			retVal = heap[1];
			heap[1] = heap[remindSize];
			--remindSize;
			perDown( 1 );

			// 赋值
			values[retVal] = val;

			return retVal;
		},
		free : function( pos ) {
			values[pos] === null;

			// 放回pos,并更新堆
			heap[++remindSize] = pos;
			perUp( remindSize );
		},
		at : function( pos ) {
			return values[pos];
		}
	};
}
